/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

//反序中序遍历，每次更新ans将ans的值赋给当前访问结点
//每个结点只遍历了一次，时间复杂度O(n)
//空间复杂度平均为O(logn),最坏情况下树退化成链表，则为O(n)
func convertBST(root *TreeNode) *TreeNode {
	ans := 0
	var dfs func(*TreeNode)
	dfs = func(t *TreeNode) {
		if t != nil {
			dfs(t.Right)
			ans += t.Val
			t.Val = ans
			dfs(t.Left)
		}
	}
	dfs(root)
	return root
}
